import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-08-17
 * Time: 11:09
 */
public class Test {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        int i = 0;
        int n = nums.length;
        while(i < n && nums[i] <= 0) {
            int slow = i+1;
            int fast = n-1;
            int target = -nums[i];
            while(slow < fast) {
                int sum = nums[slow] + nums[fast];
                if(sum > target) {
                    fast--;
                }else if(sum < target) {
                    slow++;
                }else {
                    List<Integer> list1 = new ArrayList<>();
                    list1.add(nums[i]);
                    list1.add(nums[slow]);
                    list1.add(nums[fast]);
                    list.add(list1);
                    slow++;
                    fast--;
                    while(slow < fast && nums[slow] == nums[slow-1]) slow++;
                    while(fast > slow && nums[fast] == nums[fast+1]) fast--;
                }
            }
            i++;
            while(i< n && nums[i] == nums[i-1]) i++;
        }

        return list;
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        int i = 0;
        int n = nums.length;
        Arrays.sort(nums);
        while(i < n) {
            int j = i + 1;
            long tmp1 = target-nums[i];
            while(j < n) {
                int slow = j + 1;
                int fast = n-1;
                long tmp2 = tmp1 - nums[j];
                while(slow < fast) {
                    int sum = nums[slow] + nums[fast];
                    if(sum > tmp2) {
                        fast--;
                    }else if(sum < tmp2) {
                        slow++;
                    }else {
                        List<Integer> list1 = new ArrayList<>();
                        list1.add(nums[i]);
                        list1.add(nums[j]);
                        list1.add(nums[slow]);
                        list1.add(nums[fast]);
                        list.add(list1);
                        slow++;
                        fast--;
                        while(slow < fast && nums[slow] == nums[slow-1]) slow++;
                        while(slow < fast && nums[fast] == nums[fast+1]) fast--;
                    }
                }
                j++;
                while(j < n && nums[j] == nums[j-1]) j++;
            }
            i++;
            while(i < n && nums[i] == nums[i-1]) i++;
        }

        return list;
    }

    //leetcode 209 长度最小的子数组
    public int minSubArrayLen(int target, int[] nums) {
        int slow = 0;
        int fast = 0;
        int sum = 0;
        int len = Integer.MAX_VALUE;
        while(fast < nums.length) {
            sum += nums[fast];
            while(sum >= target) {
                len = Math.min(len,fast-slow+1);
                sum -= nums[slow++];
            }
            fast++;
        }

        return len == Integer.MAX_VALUE ? 0 : len;
    }


    //leetcode 3 无重复字符的最长字串
    public int lengthOfLongestSubstring(String s) {
        int[] tmp = new int[128];
        char[] arr = s.toCharArray();
        int slow = 0;
        int fast = 0;
        int ret = 0;
        while(fast < arr.length) {
            tmp[arr[fast]]++;
            while(tmp[arr[fast]] > 1) {
                tmp[arr[slow++]]--;
            }
            ret = Math.max(ret,fast-slow+1);
            fast++;
        }

        return ret;
    }
}
